The present invention relates to an arithmetic processor capable of high-speed arithmetic operation and, more particularly, to an arithmetic processor which has a cellular array structure and which may be compactly fabricated on an LSI chip.
One type of conventional high-speed multiplier is discussed in Trans. of IECE Japan, Vol.J66-D, No. 6, 1983, pp. 683 to 690, and one type of conventional high-speed divider is discussed in Trans. of IECE Japan, Vol. J67-D, No. 4, 1984, pp. 450 to 457. That multiplier and that divider are arithmetic units each arranged to execute multiplication or division by means of combinational circuitry using the redundant binary expression (a kind of signed digit expression) in which each digit is represented by a set of elements {-1, 0, 1}. While those devices have a regular array structure and have faster arithmetic processing speeds than other types of conventional arithmetic units, no consideration is given to factors which are important for fabricating them commercially, such as a reduction in the number and size of constituent elements and use of MOS technology for a multiplier and divider which are capable of high-speed operation.
In particular, dividers in wide use today are sequential circuits each consisting of a subtracter (adder) and a shifter. However, it is well known that, as the number of digits of the operands increases, an exceedingly long time is required for those dividers to perform arithmetic operations. On the other hand, large-size computers having high-speed multipliers often employ multiplication-type division in which division is performed by repetition of multiplication. However, realization of such multiplication-type division by combinational circuitry requires large numbers of hardware elements, and is therefore impractical.
With respect specifically to a high-speed arithmetic unit employing signed digit numbers for arithmetic operation, a method has been proposed in which an arithmetic operation such as multiplication or division is realized by combinational circuitry utilizing an ECL logic element that enables NOR and OR operations to be simultaneously performed. However, exhaustive consideration has heretofore not been given to problems which must be solved to put that proposed high-speed arithmetic unit into practical use, such as reducing the number of elements required and the use of other types of circuitry to construct the unit, and, therefore, the following problems are associated with that proposed signed digit high-speed arithmetic unit:
(1) As the number of digits of the operands increases, the number of elements required increases, which makes it difficult to fabricate an arithmetic unit capable of handling a large number of digits on a single LSI chip.
(2) When the arithmetic unit is realized using, for example, a MOS circuit which cannot perform NOR and OR operations at the same time, the OR circuit is realized by elements formed in two stages, that is, a NOR gate and an inverter, and the number of stages or gates required in the arithmetic circuit increases correspondingly, resulting in an increase in operation time.